1. Field of the Invention
The present invention relates to a shape data approximation method for reducing the amount of data address of a shape model used in the field of computer graphics, in which the shape model is approximated with its general shape maintained. The present invention also relates to an information processing apparatus that executes the approximation method and a medium that provides a program for the approximation method.
2. Description of the Related Art
When a plurality of identical models are present on screen in the image rendering in the computer graphics, the same model is typically rendered regardless of the location, size, and depth of the model, a point of interest to a viewer, and speed of the movement of the model. Such shape model is called a polygon model, and is constructed of a plurality of surfaces.
The same model is not always required in the rendering. Models are switched depending on the location, size, depth of the model, a point of interest to a viewer, and the speed of the model. Not only an original detailed model, but also a more simplified model is rendered at a sufficiently high image quality.
Specifically, a graphics display apparatus has prepared models at different levels of detail, and switch them from one to another during the rendering, presenting an apparent image quality as good as that provided by the original model. Since the rendering time in the computer graphics depends on the amount of data, a model having a smaller amount of data is rendered faster than the original model. Such an arrangement satisfies two requirements at the same time, a high-speed rendering and a high-image quality rendering, normally required of computer graphics.
Techniques for creating models having different levels of detail are effective for the display of computer graphics models. If the amount of data is simply reduced to lower the level of detail of the model, the viewer may find an approximate model unnatural. To minimize the unnatural look, a general feature portion of the model is preferably left while the remaining portion is cut to reduce the amount of data. Such an approximation of the model is hitherto manually performed by designers, requiring a great deal of labor and time.
Reducing the amount of data (the number of polygons and the number of surfaces) is called a polygon reduction, a polygonal approximation, a polygon compression, or a surface simplification.
Several studies for performing the polygonal approximation, namely, surface simplification on a computer have been made. These studies treat an approximation method for a single component only, and fail to consider an approximation that maintain a positional relationship and engagement relationship between a plurality of associated components.
If the engagement relationship is destroyed in rendering components, such as gears in mesh or a top covering and a bottom covering, having an engagement relationship, the destroyed engagement relationship not only presents an unnaturally looking image to the viewer but also makes it impossible to render a plurality of components together on screen.
In a paper authored by Greg Turk, entitled xe2x80x9cRe-Tiling Polygonal Surfacexe2x80x9d (Computer Graphics, Vol. 26, No. 2, Jul. 1992), points, arranged on the surface of a polygon model, are connected to reorganize the model, and the model is thus hierarchically approximated. The algorithm presented by this paper treats a rounded object, but is inappropriate for a sharp edged shape, and is unable to cover objects of general shapes.
In a paper authored by Francis J. M. Schmitt, Brian A. Barsky, and Wen-Hui Du, entitled xe2x80x9cAn Adaptive Subdivision Method for Surface-Fitting from Sampled Dataxe2x80x9d (Computer Graphics Vol. 20, No. 4, Aug. 1986), Bezier patches are attached to a three-dimensional object for approximation. According to this paper, however, general polygons typically used in the computer graphics are not treated.
In a paper authored by Hugues Hoppe et al., entitled xe2x80x9cMesh Optimizationxe2x80x9d (Computer Graphics Proceedings, Annual Conference. Series, SIGGRAPH 1993), energy is introduced in the evaluation of a approximation model. In order to the minimize the energy, an edge removal, a patch segmentation, and an edge swapping are iterated to approximate the model. In the technique disclosed in this paper, long iterative calculations are required before a minimum energy point is found. For the point not to be trapped in a localized minimum point, some solution, such as simulated annealing, is required like other minimum energy problems. The minimum energy point is not necessarily the best in terms of the sense of vision.
In a paper authored by Hugues Hoppe, entitled xe2x80x9cViewed Dependent Refinement of Progressive Meshesxe2x80x9d (Siggraph 97 Conference Proceedings 1997), the energy of an edge is calculated, and an edge having a small energy value is removed. Furthermore, a polygon reduction is performed in accordance with a viewer""s point of view. However, an adjacency relationship between components is not considered. Michael Garland and Paul S. Heckbert disclose a polygon reduction technique in a paper entitled xe2x80x9cSurface Simplification Using Quadric Error Metricsxe2x80x9d (Siggraph 97 Conference Proceedings 1997). A distance from an apex to a surface is squared, squared distances are summed, and an edge having a smaller sum has a higher priority in removal. In this case also, the adjacency and engagement relationships between components are not considered.
These past studies of the approximation of the model fail to treat the adjacency relationship and engagement relationship.
In the conventional shape approximation, the objects to be handled are limited, a long calculation time is required, and the adjacency relationship striding over a plurality of components is not considered.
Accordingly, it is an object of the present invention to provide a shape data approximation method which approximates shape data while maintaining an adjacency relationship and engagement relationship in an adjacent region where a plurality of components are adjacent to each other, in the approximation of a shape model used in the computer graphics. It is also an object to provide an information processing apparatus that executes the approximation method and a medium that provides a program for the approximation method.
In one aspect of the present invention, the approximation method for approximating shape data at a desired level of detail to be approximate data, includes the designating step of designating an adjacent region where a plurality of components are adjacent to each other in the shape data, the evaluating step of calculating an evaluation score in accordance with the degree of deformation of the adjacent region resulting from an approximation, and the approximating step of approximating the shape data in accordance with the evaluation score to create the approximate data.
In another aspect of the present invention, the approximation method for approximating shape data at a desired level of detail to be approximate data, includes the forming step of placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, the selecting step of selecting an evaluation edge of interest for evaluation from edges constituting the shape data and the virtual edge, the evaluating step of calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and the approximating step of approximating the shape data in accordance with the evaluation score.
In yet another aspect of the present invention, the An information processing apparatus for approximating shape data at a desired level of detail to be approximate data, includes designating means for designating an adjacent region where a plurality of components are adjacent to each other in the shape data, evaluating means for calculating an evaluation score in accordance with the degree of deformation of the adjacent region resulting from an approximation, and approximating means for approximating the shape data in accordance with the evaluation score provided by the evaluating means to create the approximate data.
In yet another aspect of the present invention, the information processing apparatus for approximating shape data at a desired level of detail to be approximate data, includes forming means for placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, selecting means for selecting an evaluation edge of interest for evaluation from edges constituting the shape data and the virtual edge, evaluating means for calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and approximating means for approximating the shape data in accordance with the evaluation score.
In yet another aspect of the present invention, the information processing apparatus for approximating shape data at a desired level of detail to be approximate data, includes a storage unit for storing a program including process steps and a control circuit for executing the program in accordance with the process steps, wherein the program includes the steps of designating an adjacent region where a plurality of components are adjacent to each other in the shape data, calculating an evaluation score in accordance with the degree of deformation of the adjacent region resulting from an approximation, and approximating the shape data in accordance with the evaluation score provided by the calculating means to create the approximate data.
In yet another aspect of the present invention, the information processing apparatus for approximating shape data at a desired level of detail to be approximate data, includes a storage unit for storing a program including process steps and a control circuit for executing the program in accordance with the process steps, wherein the program includes the steps of placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge, calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and approximating the shape data in accordance with the evaluation score.
In yet another aspect of the present invention, the medium provides a program to be executed by an information processing apparatus. The program includes the steps of
designating an adjacent region where a plurality of components are adjacent to each other in the shape data, calculating an evaluation score in accordance with the degree of deformation of the adjacent region resulting from an approximation, and approximating the shape data in accordance with the evaluation score to create the approximate data.
In yet another aspect of the present invention, the medium for providing a program to be executed by an information processing apparatus. The program includes the steps of placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge, and calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and approximating the shape data in accordance with the evaluation score.
In yet another aspect of the present invention, the medium provides approximate data into which shape data is approximated at a desired level of detail. The approximate data is processed in accordance with the process that includes the steps of designating an adjacent region where a plurality of components are adjacent to each other in the shape data, calculating an evaluation in accordance with the degree of deformation of the adjacent region resulting from an approximation, and approximating the shape data in accordance with the evaluation score provided through the calculating step to create the approximate data.
In yet another aspect of the present invention, the medium provides approximate data into which shape data is approximated at a desired level of detail. The approximate data is processed in accordance with the process that includes the steps of placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge, calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and approximating the shape data in accordance with the evaluation score.
Another aspect of the present invention is the computer program under which an information processing apparatus creates approximate data by approximating shape data at a desired level of detail. The program includes the steps of designating an adjacent region where a plurality of components are adjacent to each other in the shape data, calculating an evaluation score in accordance with the degree of deformation of the adjacent region resulting from an approximation, and approximating the shape data in accordance with the evaluation score to create the approximate data.
Another aspect of the present invention is the computer program under which an information processing apparatus creates approximate data by approximating shape data at a desired level of detail. The program includes the steps of placing a virtual edge between apexes of an adjacent region where a plurality of components are adjacent to each other in the shape data, selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge, calculating an evaluation score in accordance with the degree of importance of the evaluation edge in response to a removal of the evaluation edge, and approximating the shape data in accordance with the evaluation score.